class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n];
        if(s.charAt(0) == '0'){
            return 0;
        }
        dp[0] = 1;
        if(n < 2){
            return dp[0];
        }
        if(s.charAt(0) == '1'){
            if(s.charAt(1) == '0'){
                dp[1] = 1;
            }else{
                dp[1] = 2;
            }
        }else if(s.charAt(0) == '2'){
            if(s.charAt(1) <= '6' && s.charAt(1) != '0'){
                dp[1] = 2;
            }else{
                dp[1] = 1;
            }
        }else{
            if(s.charAt(1) == '0'){
                return 0;
            }else{
                dp[1] = 1;
            }
        }
        for(int i = 2; i < n; i++){
            if(s.charAt(i - 1) > '2' || s.charAt(i - 1) == '0'){
                if(s.charAt(i) == '0'){
                    dp[i] = 0;
                    return 0;
                }else{
                    dp[i] = dp[i - 1];
                }
            }else {
                if(s.charAt(i) == '0'){
                    dp[i] = dp[i - 2];
                }else{
                    if(s.charAt(i - 1) == '1'){
                        dp[i] = dp[i - 1] + 1;
                    }else{
                        if(s.charAt(i) < '7'){
                            dp[i] = dp[i - 1] + 1;
                        }else{
                            dp[i] = dp[i - 1];
                        }
                    }
                }
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.numDecodings("226");
    }
}